% A New Constructive Ordering of the Natural Numbers % Aurey Hippa, An M. Rodriguez* % September 3, 2025 ## Abstract A constructive total order on the natural numbers is introduced based on a hereditary exponent rank computed from the prime factorization of an integer and the prime factorizations of its exponents, recursively. Each number is assigned a finite rank measuring the minimal exponent-depth needed to build it from one by prime powers and finite products. Ordering first by rank and then by magnitude yields a computable, divisibility–compatible linear extension of the divisibility partial order. The rank grows on the scale of the iterated logarithm, which implies that almost all numbers occur very early in the order. Structural characterizations, bounds, and algorithms for evaluation and enumeration are provided. ## One-Sentence Summary Order the natural numbers by the minimal hereditary depth of their exponent trees, then by size; this yields a computable, fine-grained, multiplicative–structural ordering with iterated-logarithm height. ## Keywords natural numbers, constructive order, divisibility, prime exponents, iterated logarithm, enumeration ## Introduction Standard numerical order organizes the natural numbers primarily by size, ignoring multiplicative structure. Many tasks in arithmetic and computation benefit from orderings that surface algebraic complexity—e.g., divisibility, smoothness, or exponentiation depth. A constructive scheme is presented that linearly orders the natural numbers by a **hereditary exponent rank**. The rank reflects how many exponent layers are required to assemble the number from one using prime powers and finite products. The resulting order is a linear extension of divisibility, computable, and admits quantitative control: the rank is bounded above and below by iterated logarithms of the number. This provides a principled, structure-aware alternative to size-first enumeration. ## Framework ### Basic definitions Let $\mathbb N:=\{1,2,3,\dots\}$. Every $n\in\mathbb N$ has the canonical factorization $$ n=\prod_{p} p^{\alpha_p}, $$ over primes $p$, where all but finitely many exponents $\alpha_p\in\mathbb N\cup\{0\}$ vanish. Define the **hereditary exponent rank** $r:\mathbb N\to\mathbb N$ recursively by $$ r(1):=0,\qquad r(n):=1+\max_{p\mid n} r(\alpha_p)\quad (n>1). $$ Intuitively, $r(n)$ is one plus the maximal rank among the exponents appearing in the prime factorization of $n$; exponents themselves are ranked by the same rule. For $t\in\mathbb N$, define the **rank layers** $$ \mathcal L_t:=\{\,n\in\mathbb N:\ r(n)=t\,\},\qquad \mathcal U_t:=\{\,n\in\mathbb N:\ r(n)\le t\,\}. $$ ### The constructive order Define a total order $\prec$ on $\mathbb N$ by $$ n\prec m\ \Longleftrightarrow\ \big( r(n)0$ there exists $k$ such that the set $\{n:\ \alpha_p(n)\le k\ \forall p\}$ has lower density $\ge 1-\varepsilon$, and among those, the squarefree-exponent constraint removes a proportion $O(1/k)$. These observations align with the $\Theta(\log^{*} n)$ height: almost all integers appear at very small ranks. ### Algorithms **Rank evaluation (given $n$).** 1. If $n=1$, return $0$. 2. Factor $n$ as $\prod p^{\alpha_p}$. 3. Recursively compute $r(\alpha_p)$ for each nonzero exponent $\alpha_p$. 4. Return $1+\max_p r(\alpha_p)$. This terminates since $\alpha_p1$ and recursion depth is $O(\log^{*} n)$. **Enumeration up to a bound $B$.** 1. For $t=0,1,2,\dots$: 2. For $n=1,2,\dots,B$: 3. Output $n$ if $r(n)=t$ (computed by the evaluation procedure). 4. Stop once all $n\le B$ have been output. This lists $\{1,\dots,B\}$ in the order $\prec$. For unbounded enumeration, increase $B$ as needed or generate by products $\prod p^{e_p}$ with $e_p$ drawn from previously enumerated layers, pruned by increasing numeric thresholds to avoid duplicates; tie-resolution by magnitude enforces the prescribed order. ## Results 1. **Totality.** The relation $\prec$ is a total order on $\mathbb N$. 2. **Linear extension of divisibility.** If $m\mid n$ and $m\ne n$ then $m\prec n$. 3. **Low rank characterization.** - $r(n)=0$ iff $n=1$. - $r(n)=1$ iff $n$ is squarefree and $n\ge2$. - $r(n)\le 2$ iff every exponent in the prime factorization of $n$ is squarefree. 4. **Height.** $r(n)=\Theta(\log^{*} n)$ with explicit two-sided bounds given above. 5. **Constructive closure.** $\mathcal U_{t+1}$ is the multiplicative monoid generated by $\{p^{e}:\ e\in\mathcal U_t,\ p\text{ prime}\}$. 6. **Early density.** $\mathcal U_2$ has natural density one; hence almost all integers appear by rank two, and $\prec$ lists “most” numbers immediately after the squarefree layer. Proofs have been indicated in the derivation section; full details follow directly from the recursive definition and standard multiplicative estimates. ## Discussion The hereditary exponent rank exposes multiplicative structure ignored by the usual order. The top layer ($r=1$) isolates squarefree numbers; the next ($r=2$) includes precisely those with squarefree exponents, and so on. The closure rule ensures exponent–feeding: exponents from earlier layers become exponents for new prime powers one layer later. The resulting order is computable, respects divisibility, and organizes integers by a natural complexity measure with extremely slow growth (iterated logarithm), implying shallow global height. This order interfaces cleanly with algorithms that prefer divisibility precedence (e.g., dynamic programming over divisors, multiplicative convolutions) and with analytic number theory contexts where exponent structure matters (e.g., $p$-adic valuations, smoothness, or lifting the exponent). It also offers canonical “levels” for sampling and testing number-theoretic phenomena under controlled multiplicative complexity. ## Conclusion A constructive, divisibility–compatible linear order on $\mathbb N$ has been defined via the hereditary exponent rank. The order is computed by recursion on prime-exponent trees, is a linear extension of divisibility, and has height $\Theta(\log^{*} n)$. Almost all integers appear by rank two, yet the order distinguishes fine multiplicative structure beyond mere size. The framework provides a principled alternative to numerical order when multiplicative complexity is primary. ## Next Work 1. Develop efficient, duplicate-free generators for $\mathcal L_t$ via priority queues keyed by magnitude and seeded by $p^{e}$ with $e\in\mathcal U_{t-1}$. 2. Analyze precise asymptotics of $|\mathcal U_t\cap[1,B]|$ as $B\to\infty$ for fixed $t\ge2$. 3. Extend to $\mathbb N^k$ by componentwise ranks and to $\mathbb Z$ via sign strata; study compatibility with convolution and Dirichlet series. 4. Compare with alternative complexity orders (addition–multiplication circuits, integer complexity) and examine correlations. 5. Investigate applications to sieve layers where exponent patterns govern inclusion–exclusion weights. ## Corresponding author(s) Contact: author@proton.example ## References 1. Niven, I., Zuckerman, H. S., & Montgomery, H. L. (1991). An Introduction to the Theory of Numbers (5th ed.). Wiley. 2. Hardy, G. H., & Wright, E. M. (2008). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press. 3. Tenenbaum, G. (2015). Introduction to Analytic and Probabilistic Number Theory (3rd ed.). American Mathematical Society. 4. Granville, A. (2008). Smooth numbers: computational number theory and beyond. In Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography (pp. 267–323). Cambridge University Press.